from collections import OrderedDict


class LRUCache(OrderedDict):
    def __init__(self, capacity: int):
        super().__init__()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self:
            return -1
        self.move_to_end(key)
        return self[key]

    def put(self, key: int, value: int) -> None:
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.capacity:
            self.popitem(last=False)


if __name__ == '__main__':
    # lRUCache = LRUCache(2)
    # lRUCache.put(1, 1) # 缓存是 {1=1}
    # lRUCache.put(2, 2) # 缓存是 {1=1, 2=2}
    # print(lRUCache.get(1))    # 返回 1
    # lRUCache.put(3, 3) # 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
    # print(lRUCache.get(2))    # 返回 -1 (未找到)
    # lRUCache.put(4, 4) # 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
    # print(lRUCache.get(1))    # 返回 -1 (未找到)
    # print(lRUCache.get(3))    # 返回 3
    # print(lRUCache.get(4))    # 返回 4

    pass
    lRUCache = LRUCache(2)
    lRUCache.put(2, 1)
    lRUCache.put(1, 1)
    lRUCache.put(2, 3)
    lRUCache.put(4, 1)
    print(lRUCache.get(1))
    print(lRUCache.get(2))
